package leetcode.f1t100;

/**
 * 给一个间隔为单位1的栅栏高度数组, 计算出哪两个栅栏之间可拦住最多的水位
 * https://leetcode.com/problems/container-with-most-water/
 *
 * @author lichx
 * @date 2021/10/9 15:20
 */
public class Q11_ContainerWithMostWater {
    public int maxArea(int[] height) {
        return f(height);
    }

    public static int f(int[] height) {
        int l = height.length;
        int i = 0, j = l - 1, ans = 0;
        while (i < j) {
            ans = Math.max(Math.min(height[i], height[j]) * (j - i), ans);
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }

    public static int valid(int[] height) {
        int ans = 0;
        int l = height.length;
        for (int i = 0; i < l - 1; i++) {
            for (int j = 1; j < l; j++) {
                ans = Math.max(Math.min(height[i], height[j]) * (j - i), ans);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int times = 1000;
        int size = 100;
        int maxHeight = 100;
        for (int i = 0; i < times; i++) {
            int length = (int) (Math.random() * size);
            int[] height = new int[length];
            for (int j = 0; j < length; j++) {
                height[j] = (int) (Math.random() * maxHeight);
            }
            if (valid(height) != f(height)) {
                for (int j = 0; j < height.length; j++) {
                    System.out.print(height[j] + "  ");
                    System.out.println();
                }
                return;
            }
        }
        System.out.println("finish");
        System.out.println(f(new int[]{4,3,2,1,4}));
    }
}
